package LinkedList.链表相交;

import LinkedList.ListNode;

public class Test {

    // 1.
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode A = headA, B = headB;
            while(A != B) {
                A = A != null ? A.next : headB;
                B = B != null ? B.next : headA;
            }

            return A;
        }
    }

    // 2.
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if(headA == null || headB == null) {
            return null;
        }

        ListNode n1 = headA, n2 = headB;
        int l1 = 0, l2 = 0;

        // 计算长度 让短的先走
        while(n1 != null) {
            l1++;
            n1 = n1.next;
        }
        while(n2 != null) {
            l2++;
            n2 = n2.next;
        }

        int len = 0;
        if(l1 >= l2) {
            len = l1 - l2;
            while(len != 0) {
                headA = headA.next;
                len--;
            }
        }
        if(l1 < l2) {
            len = l2 - l1;
            while(len != 0) {
                headB = headB.next;
                len--;
            }
        }

        // 此时两个链表长度相同，没有相交的话，只能 为null的时候 相同
        while(headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;

    }
}
